#include "tree.h"
#include<stdlib.h>
#include<stdio.h>
#include<queue>
using namespace std;
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (*pi > n || a[*pi] == '#')
	{
		(*pi)++;
		return 0;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL)
	{
		perror("malloc error");
		return 0;
	}
	root->_data = a[*pi++];
	root->_left = BinaryTreeCreate(a, n, pi);
	root->_right = BinaryTreeCreate(a, n, pi);

	return root;
}

void BinaryTreeDestory(BTNode** root)
{
	if (*root == nullptr)
	{
		return;
	}
	BinaryTreeDestory((&((*root)->_left)));
	BinaryTreeDestory((&((*root)->_right)));

	free(*root);
	*root = nullptr;
	
}

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right)+1;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->_left == NULL && root->_right == NULL)
	{
		return 1;
	} 
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == nullptr || k < 1)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	int leftcount = BinaryTreeLevelKSize(root->_left, k - 1);
	int rightcount = BinaryTreeLevelKSize(root->_right, k - 1);
	return leftcount + rightcount;
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == nullptr)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root;
	}
	BTNode* leftTree = BinaryTreeFind(root->_left, x);
	if (leftTree != NULL)
	{
		return leftTree;
	}
	return BinaryTreeFind(root->_right, x);

}

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL) return;
	printf("%c", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL) return;
	BinaryTreePrevOrder(root->_left);
	printf("%c", root->_data);
	BinaryTreePrevOrder(root->_right);

}

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL) return;
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
	printf("%c", root->_data);
}

void BinaryTreeLevelOrder(BTNode* root)
{
	if (root == nullptr)
	{
		return;
	}
	queue<BTNode*> nodequeue;
	nodequeue.push(root);
	while (!nodequeue.empty())
	{
		BTNode* cur = nodequeue.front();
		printf("%c", cur->_data);
		if (cur->_left != nullptr)
		{
			nodequeue.push(cur->_left);
		}
		if (cur->_right != nullptr)
		{
			nodequeue.push(cur->_right);
		}
		nodequeue.pop();
	}

}

int BinaryTreeComplete(BTNode* root)
{
	if (root == NULL)
	{
		return 1;
	}
	bool wrong = false;
	queue<BTNode*> nodequeue;
	nodequeue.push(root);
	while (!nodequeue.empty())
	{
		BTNode* cur = nodequeue.front();
		nodequeue.pop();
		if (wrong && (cur->_left == NULL || cur->_right == NULL))
		{
			return 0;
		}
		if (cur->_left == NULL && cur->_right != NULL)
		{
			return 0;
		}

		if (cur->_left != NULL)
		{
			nodequeue.push(cur->_left);
		}
		else
		{
			wrong = true;
		}

		if (cur->_right != NULL)
		{
			nodequeue.push(cur->_right);
		}
		else
		{
			wrong = true;
		}
		
	}
	return 1;

}
